package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/string-compression/">压缩字符串(String Compression)</a>
 * <p>给你一个字符数组 chars ，请使用下述算法压缩：</p>
 * <p>
 * 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：
 *     <ul>
 *         <li>如果这一组长度为 1 ，则将字符追加到 s 中。</li>
 *         <li>否则，需要向 s 追加字符，后跟这一组的长度。</li>
 *     </ul>
 * </p>
 * <p>压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。</p>
 * <p>请在 修改完输入数组后 ，返回该数组的新长度。</p>
 * <p>你必须设计并实现一个只使用常量额外空间的算法来解决此问题。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：chars = ["a","a","b","b","c","c","c"]
 *      输出：返回 6 ，输入数组的前 6 个字符应该是：["a","2","b","2","c","3"]
 *      解释："aa" 被 "a2" 替代。"bb" 被 "b2" 替代。"ccc" 被 "c3" 替代。
 *
 * 示例 2：
 *      输入：chars = ["a"]
 *      输出：返回 1 ，输入数组的前 1 个字符应该是：["a"]
 *      解释：唯一的组是“a”，它保持未压缩，因为它是一个字符。
 *
 * 示例 3：
 *      输入：chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
 *      输出：返回 4 ，输入数组的前 4 个字符应该是：["a","b","1","2"]。
 *      解释：由于字符 "a" 不重复，所以不会被压缩。"bbbbbbbbbbbb" 被 “b12” 替代。
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>1 <= chars.length <= 2000</li>
 *     <li>chars[i] 可以是小写英文字母、大写英文字母、数字或符号</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/1 16:50
 */
public class LC0443StringCompression_M {
    static class Solution {
        public int compress(char[] chars) {
            // 当前字符第一次出现的位置
            int leftIndex = 0;
            // chars回写的下一个位置
            int writeIndex = 0;
            int length = chars.length;
            // read：当前所在位置
            for (int read = 0; read < length; read++) {
                // 如果到了最后一个字符 或者 当前字符和下一个字符不一样，进行汇总
                if (read == length - 1 || chars[read] != chars[read + 1]) {
                    // 1.回写字符
                    chars[writeIndex++] = chars[read];
                    // 当前字符的数量。如果只出现一次是不需要处理的
                    int count = read - leftIndex + 1;
                    if (count > 1) {
                        // 2.回写字符：将数量的逆序先回写到chars中，之后进行反转。
                        int start = writeIndex;
                        while (count > 0) {
                            // count % 10 得到是个位上的数字
                            chars[writeIndex++] = (char) (count % 10 + '0');
                            count /= 10;
                        }
                        reverse(chars, start, writeIndex - 1);
                    }
                    leftIndex = read + 1;
                }
            }
            return writeIndex;
        }

        private void reverse(char[] chars, int left, int right) {
            while (left < right) {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                ++left;
                --right;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        char[] chars1 = {'a', 'a', 'b', 'b', 'c', 'c', 'c'};
        System.out.println(new String(chars1, 0, solution.compress(chars1)));

        char[] chars2 = {'a'};
        System.out.println(new String(chars2, 0, solution.compress(chars2)));

        char[] chars3 = {'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'b'};
        System.out.println(new String(chars3, 0, solution.compress(chars3)));
    }
}
